// https://leetcode.cn/problems/delete-and-earn/

// 算法思路总结：
// 1. 将问题转化为打家劫舍模型
// 2. 统计每个数字的总价值，相邻数字不能同时选择
// 3. 使用动态规划求不相邻元素的最大和
// 4. 时间复杂度：O(n + k)，空间复杂度：O(k)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    const int N = 1e4 + 1;
    int deleteAndEarn(vector<int>& nums) 
    {
        sort(nums.begin(), nums.end());

        int n = nums.size();
        if (n == 0) return 0;
        if (n == 1) return nums[0];

        vector<int> arr(N, 0);
        for (const int& num : nums)
            arr[num] += num;

        int m = arr.size();
        int prev = 0, cur = 0;
        for (int i = 0 ; i < m ; i++)
        {
            int temp = cur;
            cur = max(cur, prev + arr[i]);
            prev = temp;
        }
        return cur;
    }
};

int main()
{
    vector<int> v1 = {3,4,2}, v2 = {2,2,3,3,3,4};
    Solution sol;

    cout << sol.deleteAndEarn(v1) << endl;
    cout << sol.deleteAndEarn(v2) << endl;

    return 0;
}